
"""
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。
走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

冒泡法简单的说就是：
交换排列。
两两比较大小，交换位置。
结果分为升序和降序排列。
"""
def test01():
    lst = []
    count = 0
    while True:
        num = int(input('>>>'))
        # 终止判断，88 跳出
        if num == 88:
            break
        lst.append(num)
        if count == 0:
            count = count + 1
            continue
        if lst[count - 1] >= lst[count]:
            a = lst[count]
            lst[count] = lst[count - 1]
            lst[count - 1] = a
            count = count + 1
        else:
            count = count + 1
    print(lst)
    print(lst[count - 1])


"""
思路：
两层循环解决：外层循环控制次数，应该等同列表元素的个数；内层循环控制交换，从头到尾依次和自己+1的元素进行比较。
可能外循环执行到某次已经使整个列表排序好，可以统计交换次数是否为0来决定退出。
"""
def test02():
    num_lst = [1, 9, 8, 5, 6, 7, 4, 3, 2]
    num_lst1 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    l = len(num_lst1)
    for i in range(l):
        for j in range(l - i - 1):
            if num_lst[j] > num_lst[j + 1]:
                tmp = num_lst[j + 1]
                num_lst[j + 1] = num_lst[j]
                num_lst[j] = tmp
    print(num_lst)

"""
加入count：
count_exter来统计外层循环次数。
count_inter来统计内层循环次数。
"""
def test03():
    num_lst = [1, 9, 8, 5, 6, 7, 4, 3, 2]
    num_lst1 = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    l = len(num_lst)
    count_exter = 0
    count_inter = 0
    for i in range(l):
        count_exter += 1
        for j in range(l - i - 1):
            if num_lst[j] > num_lst[j + 1]:
                tmp = num_lst[j + 1]
                num_lst[j + 1] = num_lst[j]
                num_lst[j] = tmp
                count_inter += 1

    l1 = len(num_lst1)
    count_exter1 = 0
    count_inter1 = 0
    for i in range(l1):
        count_exter1 += 1
        for j in range(l - i - 1):
            if num_lst1[j] > num_lst1[j + 1]:
                tmp = num_lst1[j + 1]
                num_lst1[j + 1] = num_lst1[j]
                num_lst1[j] = tmp
                count_inter1 += 1

    print(num_lst, count_exter, count_inter)
    print(num_lst1, count_exter1, count_inter1)

"""
根据count进行优化：

就是，只要内循环交换至少一次，flag就是True，就不会break；如果内循环一次都没有交换，flag就是False，就会break。
"""
def test04():
    num_lst = [1, 9, 8, 5, 6, 7, 4, 3, 2]

    l = len(num_lst)
    count_exter = 0
    count_inter = 0
    for i in range(l):
        count_exter += 1
        flag = False
        for j in range(l - i - 1):
            if num_lst[j] > num_lst[j + 1]:
                tmp = num_lst[j + 1]
                num_lst[j + 1] = num_lst[j]
                num_lst[j] = tmp
                count_inter += 1
                flag = True
        if not flag:
            break
    print(num_lst, count_exter, count_inter)

# 最后
def testmain():
    num_lst = [1, 9, 8, 5, 6, 7, 4, 3, 2]

    l = len(num_lst)
    count_exter = 0
    count_inter = 0
    for i in range(l):
        count_exter += 1
        flag = False
        for j in range(l - i - 1):
            if num_lst[j] > num_lst[j + 1]:
                num_lst[j], num_lst[j + 1] = num_lst[j + 1], num_lst[j]
                flag = True
        if not flag:
            break
    print(num_lst, count_exter, count_inter)

# 测试：
testmain()
